public class Main {
    /**
     * 不同路径----记忆搜索解决
     */
    class Solution {

        public int uniquePaths(int m, int n) {
            int[][] memo = new int[m + 1][n + 1];
            //初始备忘录值为-1
            return dfs(m,n,memo);
        }
        int dfs(int i, int j, int[][] memo) {
            if(memo[i][j] != 0) {
                //说明备忘录里面已经有记录了 将该次递归剪枝掉
                return memo[i][j];
            }
            if(i == 0 || j==0) {
                return 0;
            }
            if(i == 1 && j == 1) {
                memo[i][j] = 1;
                return 1;
            }
            memo[i][j] = dfs(i, j - 1, memo) + dfs(i - 1, j, memo);
            return dfs(i, j - 1,memo) + dfs(i - 1, j,memo);
        }
    }

    /**
     *
     * 猜数字游戏
     */
   /* class Solution {
        int[][] memo;
        public int getMoneyAmount(int n) {
            memo = new int[n + 1][n + 1];
            return dfs(1,n);
        }
        int dfs(int left, int right) {
            if(left >= right) return 0;
            if(memo[left][right] != 0) {
                return memo[left][right];
            }
            int ret = Integer.MAX_VALUE;
            for(int head = left; head <= right; head++) {
                int x = dfs(left, head - 1);
                int y = dfs(head + 1, right);
                ret = Math.min(ret, Math.max(x, y) + head);
            }
            memo[left][right] = ret;
            return ret;
        }
    }*/

    /**
     * 矩阵中的最长递增路径
     */
    /*class Solution {
        int[] dx = { 0, 0, -1, 1 };
        int[] dy = { 1, -1, 0, 0 };
        int m, n;
        int[][] memo;

        public int longestIncreasingPath(int[][] matrix) {
            m = matrix.length;
            n = matrix[0].length;
            int ret = Integer.MIN_VALUE;
            memo = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    ret = Math.max(dfs(matrix, i, j), ret);
                }
            }
            return ret;
        }

        int dfs(int[][] matrix, int i, int j) {
            int ret = 1;
            if(memo[i][j] != 0) {
                return memo[i][j];
            }
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n  && matrix[x][y] > matrix[i][j]) {
                    ret = Math.max(dfs(matrix, x, y) + 1, ret);
                }
            }
            memo[i][j] = ret;
            return ret;
        }
    }*/





}
